package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月8日
*时间：下午2:42:49
*/
public class Q81 {
    /**
     * @param nums: A list of integers.
     * @return: the median of numbers
     */
    public int[] medianII(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return null;
        }
        int length = nums.length;
        int[] rs = new int[length];
        int sort[] = new int[length];
        sort[0] = nums[0];
        rs[0] = nums[0];
        for (int i = 1; i < length; i++) {
            insert(i, nums, sort);
            rs[i] = sort[i / 2];
        }
        return rs;
    }

    private void insert(int i, int[] nums, int[] sort) {
        int k = nums[i];
        for (int j = 0; j < i; j++) {
            if (k < sort[j]) {
                for (int p = i; p > j; p--) {
                    sort[p] = sort[p - 1];
                }
                sort[j] = k;
                return;
            }
        }
        sort[i] = k;
    }

    @Test
    public void testA() {
        int[] nums = { 2, 20, 100 };
        int[] rs = medianII(nums);
        for (int i : rs) {
            System.out.println(i);
        }

    }
}
